1) Field of the Invention
The present invention relates to a technique for decoding and decompressing compressed data obtained, for example, by modified-modified READ (MMR) coding (where READ is an acronym for relative element address designate).
2) Description of the Related Art
Still images, such as text images, etc., which are dealt with by a facsimile apparatus are basically images expressed with two levels, a white level and a black level. The still images are constructed of binary image data. In the binary text images to be dealt with by a facsimile apparatus, consecutive white pixels or black pixels often appear.
Hence, for a large quantity of binary image data, a data compression process is performed by coding consecutive white or black pixels at a place where they change to a black or white pixel, using MMR coding.
FIG. 27 schematically shows a general data compressing unit for carrying out such a data compression process by MMR coding.
As shown in the figure, the input side of the data compressing unit 1 is connected with an uncompressed data storage section 2, while the output side is connected to a compressed data storage section 3.
The data compressing unit 1 is constructed of an input buffer 4, a compressing section 5, an output buffer 6, and a reference table holding section 7.
The uncompressed data storage section 2 stores, for example, binary image data (uncompressed data; data to be compressed) read for document transmission. The compressed data storage section 3 stores image data (compressed data) coded by the data compressing unit 1.
In the compression process within the data compressing unit 1, binary image data sampled at 8 bits per 1 mm, for example, are input to the input buffer 4 and sent to the compressing section 5. The compressing section 5 refers to the modified Huffman (MH) code table or modified READ (MR) code table held in the reference table holding section 7, and codes the input image data. The coded data (compressed data) are sent to the output buffer 6 and stored in the compressed data storage section 3.
Now, the process of coding and compressing binary image data will be described with reference to FIGS. 28 to 31 and Table 1 (two-dimensional code table). Table 1 is stored as an MR code table in the reference table holding section 7.
TABLE 1ModePixel to be codedSymbolCodePassb1, b2P0001HorizontalA0, a1, a2H001 + M(a0a1) + M(a1a2)Verticala1 justa1b1 = 0V(0)1under b1a1 to thea1b1 = 1Vr(1)011right of b1a1b1 = 2Vr(2)000011a1b1 = 3Vr(3)0000011a1 to thea1b1 = 1V1(1)010left of b1a1b1 = 2V1(2)000010a1b1 = 3V1(3)0000010
FIGS. 28 to 31 schematically show the bit sequence of the binary image data input from the uncompressed data storage section 2 to the input buffer 4, a single square denoting a single 1-bit pixel. A white square denotes a white pixel and a shaded square denotes a black pixel. The top line is the reference line, while the bottom line is the coding line. The reference line is the immediately prior image data bits, coded and transmitted from the output buffer 6 to the compressed data storage section 4. The coding line is the current image data bits input from the uncompressed data storage section 2 to the input buffer 4.
In MMR coding, a change in the color of a pixel on the coding line is judged from left to right in FIGS. 28 to 31. When a change from a white pixel to a black pixel is made, the position of the black pixel (color-changed pixel) is coded and the distance between the position of the black pixel and the position of a color-changed pixel on the reference line is coded. Similarly, when a change from a black pixel to a while pixel is made, the position of the white pixel (color-changed pixel) is coded and the distance between the position of the white pixel and the position of a color-changed pixel on the reference line is coded. Therefore, there is a need to detect the positions of color-changed pixels a0, a1, and a2 on the coding line and the positions of color-changed pixels b1 and b2 on the reference line. The color-changed pixel refers to a pixel that differs in color from its left neighbor on the same scanning line.
In the coding line, a0 is a pixel designated as a start color-changed pixel, a1 is the first color-changed pixel which is to the right of the start color-changed pixel a0, and a2 is the first color-changed pixel which is to the right of the color-changed pixel a1. At the head of the coding line, a virtual white pixel that is positioned to the left of the first pixel is assumed to be a0. In the reference line, b0 is a pixel (start color-changed pixel) which is located right above the start color-changed pixel a0, b1 is the first color-changed pixel that is to the right of the start color-changed pixel a0, and is of color opposite to a0, and b2 is the first color-changed pixel that is to the right of the color-changed pixel b1.
Next, a description will be given of the coding of the coding line based on the reference line. In the coding, a pass mode, a vertical mode, or a horizontal mode is employed depending on the positional relationship between the start color-changed pixel a0 and the reference color-changed pixel a1, a2, b1, or b2.
The pass mode is a mode that is selected when the pixel b2 is to the left of the pixel a1. In this pass mode, the pixel a0 is repositioned to the pixel just under the pixel b2. In this case, symbolic code P (code 0001), which is listed in Table 1, is transmitted.
In FIG. 28, the immediately prior coding is performed in the pass mode, and the pixel a0 is repositioned to the pixel just under the pixel b2 positioned during the previous coding. An example of pass-mode coding is shown in FIG. 29. Since the pixel b2 during the current coding is to the left of the pixel a1, the current coding (of the pixels b1 and b2) is performed in the pass mode. That is, code P (code 0001) is transmitted to the output buffer 6. Following the processing of this code, the pixel just under the pixel b2 is set as the start pixel a0 for the next coding.
The vertical mode is a mode that is selected when the pixel b2 is at the same position as the pixel a1 or to the right of the pixel a1 and the relative distance |a1b1| between the pixels a1 and b1 is less than or equal to 3 pixels. When it arises, coding with respect to the pixel a1 is performed with the relative distance |a1b1| corresponding to one of seven values (codes 1, 011, 000011, 0000011, 010, 000010, and 0000010) denoted by symbolic codes V(0), Vr(1), Vr(2), Vr(3), Vl(1), Vl(2), and Vl(3), as listed in Table 1. After the coding, the start pixel a0 for the next coding is repositioned to the pixel a1 positioned during the current coding. The letter “r” in the symbolic code indicates that the pixel a1 is to the right of the pixel b1 . The “l ” in the symbolic code indicates that the pixel a1 is to the left of the pixel b1 . The numeral within the parenthesis indicates the relative distance (number of pixels).
In the example shown in FIG. 28, the pixel b2 is to the right of the pixel a1, also the pixel a1 is to the left of the pixel b1, and the relative distance |a1b1| is 1 pixel. Therefore, MMR coding is performed in the vertical mode, and the code 010 corresponding to the symbolic code Vl(1) is transmitted to the output buffer 6. Thereafter, the pixel a1 during the current coding is set as the start pixel a0 for the next coding, and the pixels a2 and b2 are set as the pixels a1 and b1 for the next coding, respectively. If the pixels a0, a1, and b1 are repositioned in this manner, the pixel b2 is to the right of the pixel a1 and the relative distance |a1b1| is 0, as shown in FIG. 31. Thus, the next coding is similarly performed in the vertical mode. The code 1 corresponding to the symbolic code V(0) is transmitted to the output buffer 6.
Another example of vertical mode coding is shown in FIG. 30. In the example shown in the figure, the pixel b2 is to the right of the pixel a1, also the pixel a1 is to the right of the pixel b1, and the relative distance |a1b1| is 2 pixels. Thus, MMR coding is performed in the vertical mode, and the code 000011 corresponding to the symbolic code Vr(2) is transmitted to the output buffer 6.
On the other hand, the horizontal mode, as shown in FIG. 31, is a mode that is selected when the pixel b2 is at the same position as the pixel a1 or to the right of the pixel a1 and the relative distance |a1b1| between the pixels a1 and b1 is greater than or equal to 3 pixels. In FIG. 31, the relative distance |a1b1| is 4 pixels. As listed in Table 1, the distance a0a1 between the pixel a0 and the pixel a1 and the distance a1a2 between the pixel a1 and a2 are obtained, then the values M(a0a1) and M(a1a2) corresponding to these distances a0a1 and a1a2 are read out from the MH code table held in the reference table holding section 7, and coding with respect to the pixels a0, a1, and a2 is performed by symbolic code H (code 001+M(a0a1)+M(a1a2)). After the coding, the start pixel a0 for the next coding is repositioned to the pixel a2 positioned during the current coding.
An example of horizontal mode coding is shown in FIG. 31. In the example shown in the figure, the pixel b2 is to the right of the pixel a1, and the relative distance |a1b1| is 4 pixels. Thus, coding is performed in the horizontal mode. That is, because a0a1=8 and a1a2=4, the code=001+M(8)+M(4) corresponding to the symbolic code H is transmitted to the output buffer 6. The pixel a2 is repositioned to the start pixel a0 for the next coding.
In this manner, the image data shown in FIG. 28 is coded like “. . . 00010101 . . . .” That is, image data is coded based on the position of a color-changed pixel on the coding line, the position of a color-changed pixel on the reference line, and the distance between the two pixels.
The above-mentioned coding procedure (operation of the compressing section 5) will be described according to a flowchart (steps S11 to S28) shown in FIG. 32. First, suppose the pixels on the reference line are all white (step S11). Then, the first coding line is set (step S12) and the start pixel a0 is positioned as a virtual white pixel to the left of the first pixel (step S13).
Thereafter, pixels a1, b1, and b2 are detected (steps S14 to S16) and it is judged whether or not the pixel b2 is to the left of the pixel a1 (step S17). If it is to the left (route “YES” in step S17), the above-mentioned pass-mode coding is performed (step S18) and the pixel just under the pixel b2 is set as the start pixel a0 for the next coding (step S19).
When the pixel b2 is at the same position as the pixel a1 or to the right of the pixel a1 (route “NO” in step S17), it is judged whether or not the relative distance |a1b1| is less than or equal to 3 pixels (step S20).
When the relative distance |a1b1| is 3 pixels or less (route “YES” in step S20), the above-mentioned vertical mode coding is performed (step S21) and the pixel a1 during the current coding is set as the start pixel a0 for the next coding (step S22).
On the other hand, when the relative distance |a1b1| is 4 pixels or greater (route “NO” in step S20), a pixel a2 is detected (step S23) and the above-mentioned horizontal mode coding is performed (step S24). The pixel a2 during the current coding is set as the start pixel a0 for the next coding (step S25).
Next, it is judged whether or not the coding process has been executed up to the last pixel on the coding line. That is, it is judged whether or not the coding position has reached end-of-line (EOL) (step S26). If it has not reached (route “NO” in step S26), the process returns to step S14 and repeatedly carries out the above-mentioned steps S14 to S26.
If it has reached EOL (route “YES” in step S26), it is judged whether or not the coding process has been executed up to the end of image data to be coded. That is, it is judged whether or not the coding position has reached end-of-data (EOD) (step S27). If it has not reached EOD (route “NO” in step S27), the process returns to step S12 and repeatedly carries out the above-mentioned steps S12 to S27. When it arises, in step 12 the next coding line is extracted and the previous coding line is set as the reference line. If it has reached EOD (route “YES” in step S27), the coding process ends.
When decompressing the image data compressed as described above, the coded data corresponding to each line (coding line) is serially read out from the head thereof, and the decoding process is carried out according to a recognized mode.
FIG. 33 schematically shows a general data decompressing unit for carrying out such a decoding process.
As shown in the figure, the input side of the data decompressing unit 11 is connected with a compressed data storage section 12, while the output side is connected to a decompressed data storage section 13.
The data decompressing unit 11 is constructed of an input buffer 14, a decompressing section 15, an output buffer 16, and a reference table holding section 17.
The compressed data storage section 12 stores image data coded (or compressed), for example, by the above-mentioned data compressing unit 1. The decompressed data storage section 13 serially stores image data decoded (or decompressed) by the data decompressing unit 11.
In the decompression process within the data decompressing unit 11, compressed data are input to the input buffer 14 and sent to the decompressing section 15. The decompressing section 15 recognizes a mode by the code of the input data, refers to the modified Huffman (MH) code table or modified READ (MR) code table (see the two-dimensional code table in Table 1) held in the reference table holding section 17, and decodes the input data according to the recognized mode. The decoded data (decompressed data) are sent to the output buffer 16 and stored in the decompressed data storage section 13.
The decoding procedure in the decompressing section 15 will be described according to a flowchart (steps S31 to S47) shown in FIG. 34. First, suppose the pixels on a reference line are all white (step S31) Then, the first decoding line is set (step S32) and the start pixels a0 and b0 are positioned as virtual white pixels to the left of the first pixel of the reference line and the left of the first pixel of the decoding line (step S33).
The coded data corresponding to the decoding line is serially read out from the head thereof, and the coding mode is recognized according to both the code in the coded data and the two-dimensional code table (see Table 1) held in the reference table holding section 17 (step S34).
When, in step S34, the mode is recognized to be a pass mode (code 0001; route “PASS”), a pixel b2 on the reference line relative to a start pixel b0 is first detected (step S35). If the pixel b2 is detected, pixels of the color of a0 are laid down on the decoding line up to the position of the pixel b2, whereby a decoding process corresponding to the pass mode is carried out (step S36) Next, on the decoding line, the pixel just under the pixel b2 is set as the next start pixel a0 (step S37). The color of the next start pixel a0 is set to the color of the pixel b2 (step S38).
When, in step S34, the mode is recognized to be a horizontal mode (code 001; route “HORIZONTAL”), a one-dimensional decoding process is carried out by both the code M(a0a1)+M(a1a2) following the code 001 and the MH code table stored in the reference table holding section 17 (step S39). Next, a pixel a2 on the decoding line is detected and the pixel a2 is set as the next start pixel a0 (step S40). The next start pixel a0 employs the color of the previous start pixel a0 (step S41).
When, in step S34, the mode is recognized to be a vertical mode (route “VERTICAL”), a pixel b1 on the reference line relative to the start pixel b0 is first detected (step S42). If the pixel b2 is detected, a decoding process corresponding to the recognized code is carried out (step S43). More specifically, when the recognized code is 1 (V(0)), pixels of the color of a0 are laid down up to but not including the pixel b1 . When the recognized code corresponds to code Vx(n) (where x=r or l and n=1, 2, or 3), pixels of the color of a0 are laid down up to the nth pixel on the x-side (where x=r denotes the right and x=l denote the left) of the pixel b1 . Similarly, then th pixel is not included. Next, the pixel a1 on the decoding line is set as the next start pixel a0 (step S44). The next start pixel a0 employs the color opposite to the color of the previous pixel a0 (step S45).
After step S38, S41, or S45, it is judged whether or not the decoding process has been carried out up to the end of the decoding line (coded data corresponding to this line). That is, it is judged whether or not the decoding position has reached end-of-line (EOL) (step S46). If it has not reached EOL (route “NO” in step S46), the process returns to step S34 and repeatedly carries out the above-mentioned steps S34 to S46.
If it has reached EOL (route “YES” in step S46), it is judged whether or not the decoding process has been executed up to the end of the image data to be decoded. That is, it is judged whether or not the decoding position has reached end-of-data (EOD) (step S47). If it has not reached EOD (route “NO” in step S46), the process returns to step S32 and repeatedly carries out the above-mentioned steps S32 to S47. When it arises, in step 32 the next decoding line is set and the coded data corresponding to the line is read out. In addition, the previous decoding line, as it is, is set as the reference line. If it has reached EOD (route “YES” in step S47), the decoding process ends.
Problems to be solved by the present invention will occur in the case in which data compressed by the above-mentioned MMR coding is decoded and decompressed according to the procedure shown in FIG. 34.
In the case of high-resolution image data, the distance from the start pixel b0 on the reference line to the pixel b1 (or distance from the pixel b1 to the pixel b2) is long, as shown in FIG. 35. The number of bits between these pixels b0, b1, and b2 is considerably increased.
In the conventional data decompressing technique, a processing section, such as a CPU, etc., judges the color of the start pixel b0 and continues to judge each pixel (each bit) until the pixel b1 is detected. If the pixel b1 is detected, the number of judged pixels is calculated as the distance between the pixel b0 and the pixel b1 (see step S42 in FIG. 34).
This procedure will be described in detail with reference to FIG. 35. Note in the figure that a white square denotes a white pixel and a shaded square denotes a black pixel.
First, a bit at which the start pixel b0 is positioned is taken out and the color is judged. In the example shown in FIG. 35, the pixel is judged to be a white pixel. Next, the processing section judges the color of the pixel that is to the right of the pixel b0, and continues to judge the color of each pixel until a black pixel is detected. The pixel at the position where the black pixel is detected becomes the pixel b1 . In the example shown in FIG. 35, the number of pixels (bits) judged to detect the position of the pixel b1 is 20, which denotes the distance between the pixel b0 and the pixel b1.
When detecting not only the pixel b1 but also the pixel b2 (see step S35 in FIG. 34), or when detecting the pixel a1 or a2 from the position of the start pixel a0 after decoding (see step S44 or S40 in FIG. 34), the pixels b2, a1, and a2 are similarly detected while the color of each pixel (bit) is being judged.
Therefore, as the resolution of still image becomes higher, the distance (number of pixels) between pixels b0, b1, and b2 on the reference line, or the distance (number of pixels) between a0, a1, and a2 on the line decoded in the horizontal mode, becomes considerably longer. Because of this, the number of judged bits is increased and the decoding process (decompressing process) is extremely time-consuming.
In step 34 of FIG. 34, when recognizing a coding mode from the code contained in the compressed data, there is also a need to detect the number of consecutive zeros (white pixels) that are present in the data bits of compressed data (coded data). For instance, in the case of 3 consecutive 0s, the coding mode is recognized to be a pass mode. In the case of 2 consecutive 0s, the coding mode is recognized to be a horizontal mode. In the case of 0, or in the case of 4 or 5 consecutive 0s, the coding mode is recognized to be a vertical mode. Thus, when recognizing a coding mode, the number of 0s is detected by judging the color of each bit, as with the case when detecting a color-changed pixel. Therefore, the process of recognizing a coding mode (code) is time-consuming and results in an increase in the time required for the decoding process (decompressing process).